package src.BlueBridge.DeepRecursion;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 * 编写一个方法，确定某集合的所有子集
 *
 * 给定一个int数组A和数组的大小int n，请返回A的所有非空子集
 * 保证A的元素个数小于等于20，且元素互异
 *
 * 各个子集内部从大到小排列，子集之间字典逆序排序
 *
 * 其实就是选和不选的问题
 */

public class _5非空子集 {
    public static void main(String[] args) {
        int[] A = {1, 2, 3};
        Set<Set<Integer>> sets = getSubsets(A, A.length);
        System.out.println(sets);
    }

    // 递归增量构造解法
    public static Set<Set<Integer>> getSubsets(int[] A, int n) {
        // 多加的一个参数是标志当前在操作第几位
        return getSubsetsCore(A, n, n - 1);
    }
    public static Set<Set<Integer>> getSubsetsCore(int[] A, int n, int cur) {
        Set<Set<Integer>> newSet = new HashSet<>();
        if (cur == 0) {// 处理第一个元素
            // 空集
            Set<Integer> nil = new HashSet<>();
            // 添加第一个元素的集合
            Set<Integer> first = new HashSet<>();
            first.add(A[cur]);
            // 将这两个集合加到大的集合中
            newSet.add(nil);
            newSet.add(first);
            return newSet;
        }
        Set<Set<Integer>> oldSet = getSubsetsCore(A, n, cur - 1);
        for (Set<Integer> set : oldSet) {
            // 对于每个子集，cur这个元素可以加进去，也可以不加进去
            // 保留原样
            newSet.add(set);
            // 将原来的每个子集都克隆一份再添加
            Set<Integer> clone = (Set<Integer>)((HashSet)set).clone();
            // 添加当前元素
            clone.add(A[cur]);
            newSet.add(clone);
        }
        return newSet;
    }

    // 逐步生成迭代大法
    public static Set<Set<Integer>> getSubsets1(int[] A, int n) {
        Set<Set<Integer>> targetSet = new HashSet<>();
        // 加入空集
        HashSet<Integer> nil = new HashSet<>();
        targetSet.add(nil);
        if (n == 0) {
            return targetSet;
        }
        // 从第一个元素开始处理
        for (int i = 0 ; i < A.length ; i++) {
            // 新建一个大集合
            Set<Set<Integer>> res_new = new HashSet<>();
            // 把原来集合中的每个子集都加入到新集合中
            res_new.addAll(targetSet);
            // 遍历之前的集合，全部克隆一遍
            for (Set e : targetSet) {
                Set clone = (Set)((HashSet)e).clone();
                // 加入当前元素
                clone.add(A[i]);
                res_new.add(clone);
            }
            targetSet = res_new;
        }
        return targetSet;
    }

    // 二进制解法
    public static ArrayList<ArrayList<Integer>> getSubsets2(int[] A, int n) {
        return new ArrayList<>();
    }
}
